import java.util.HashSet;
//字符串的全部子序列
//测试链接 :  https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class Subsequences {
    public String[] generatePermutation (String s) {
        char[] arr = s.toCharArray(); //转化为字符数组；
        HashSet<String> set  = new HashSet<>(); //存放答案用作去重
        func(arr,0,new StringBuilder(), set);
        int n = set.size();

        String[] ans = new String[n];
        int i = 0;
        for(String temp : set){
            ans[i++] = temp;
        }

        return ans;
    }

    public void func(char[] arr, int pos, StringBuilder path, HashSet<String> set){
        if(pos == arr.length){ //走到最后的位置了
            set.add(path.toString());
        }else{
            path.append(arr[pos]);
            func(arr,pos+1,path,set);
            path.deleteCharAt(path.length()-1); //恢复现场
            func(arr,pos+1,path,set);
        }
    }

    public String[] generatePermutation2 (String s) {
        char[] arr = s.toCharArray(); //转化为字符数组；
        HashSet<String> set  = new HashSet<>(); //存放答案用作去重
        func2(arr,0,new char[arr.length],0, set);
        int n = set.size();

        String[] ans = new String[n];
        int i = 0;
        for(String temp : set){
            ans[i++] = temp;
        }

        return ans;
    }

    public void func2(char[] arr, int pos, char[] path,int size, HashSet<String> set){
        if(pos == arr.length){ //走到最后的位置了
            set.add(String.valueOf(path,0,size));
        }else{
            path[size] = arr[pos];
            func2(arr,pos+1,path,size+1,set);
            func2(arr,pos+1,path,size,set);

        }
    }
}
